package PRIO;

import java.util.Arrays;

public class TestHeap {

    //-------------数据元素准备-------------

    //创建空数组存储堆元素
    public int[] elem;

    //初始化数组大小,用于记录数组大小的变化
    public int usedSize;

    //调用构造方法,初始化数组大小为10
    public TestHeap(int[] elem) {
        this.elem = new int[10];
    }

    //初始化数组,将每一个元素加入到数组里面
    public void initElem(int[] array){
        for(int i = 0 ; i < array.length ; i++){
            elem[i]  = array[i];
            usedSize++;
        }
    }

    //-------------创建大堆-----------------
     // 大堆特点:每个子树的根节点都大于其左右子节点
    // 每颗子树结束的位置实际上就是 usedSize当usedSize < 数组长度时说明,整棵树都调整完了,就是大堆树了
    /*
    parent:每颗子树的根节点
    usedSize:每颗子树结束的位置,也就是最后一个节点的位置
     */
    public void createBigHeap(){
        //创建之前,先找到最后一个子节点的父母节点,然后每次通过循环遍历,前面的叶子节点的父母节点
        for(int parent = (usedSize - 1 - 1) / 2 ; parent >= 0 ; parent--){
            shiftDown(parent , usedSize);
        }
    }

    //位置调整的方法
    /*
    end:就是每棵树结束的位置
    child:左孩子
    child + 1 : 右孩子
     */
    private void shiftDown(int parent , int end){
        //根据根节点和孩子节点的关系,我们可以得到孩子节点的下标
        int child = 2*parent + 1;

        //===找左右最大值的下标:Child===
        //当我们的child＜end时说明没调完树的节点位置,大于end说明调完了
        while(child  < end){
            //根据树孩子节点和元素大小之间的关系:
            // --存在右孩子的条件是:右孩子的下标 < 树的总结点大小
            //在存在右孩子的条件下,我们才能去比较左右孩子的大小
            if(child + 1 < usedSize && elem[child] < elem[child + 1]){
                child++;
            }//通过上面的条件获取 左右孩子中最大值的下标


            //如果没有右孩子就不会走上面的条件判断,直接往下面走

            //===将根节点和左右最大值进行交换===
            //交换完以后;parent和child都需要往后遍历:parent = child ; child = 2*parent + 1 ;
            if(elem[child] > elem[parent]){
                //交换节点逻辑:
                //孩子大于父亲,交换两个节点
                swap(child , parent);
                parent = child;//交换完,parent往孩子节点遍历
                child = 2 * parent + 1;//孩子节点也要往父母节点的子节点移动
            }else{
                break;
            }
        }
    }

    //交换下标的方法:
    private void swap(int i , int j){
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }

    //优先级队列的删除-删除堆的元素,一定是删除堆顶元素,也就是0位置的元素
    public int poll(){
        int dele = elem[0];
        swap(0,usedSize-1);
        usedSize--;
        shiftDown(0,usedSize);
        return dele;
    }


    //插入元素

    public void offer(int val){
        //1.判断满
        if(isFull()){
            //扩容
            this.elem = Arrays.copyOf(elem, 2*elem.length);
        }
        //2.插入元素
        elem[usedSize]= val;
        usedSize++;
        //3.开始向上调整
        siftup(usedSize - 1);
    }

    public void siftup(int child){
        int parent = (child - 1) / 2;
        while(child > 0){//说明树没调整完
        //将左右孩子最大值和根节点进行比较
            if(elem[child] > elem[parent]){
                swap(child , parent);
                child = parent;
                parent = (child - 1) / 2;
            }else{
                break;
            }
        }
    }

    public boolean isFull(){
        return usedSize == elem.length;
    }

    //堆排序 -> 1.先变成大根堆 ; 2.将最后一个一个元素和堆顶元素交换; 交换完再调整成为大根堆,最后一个已经交换的值不动,
    // 将其前面的继续进行交换,直到child等于0
    public void heapSort(){
        int end = usedSize - 1;
        while(end > 0){//end为最后一个节点的下标
            swap(0,end);//交换堆顶元素和最后一个节点的值
            shiftDown(0,end - 1);//换好了,最后一个不动,前面的未换的继续所以是end-1
            end--;
        }
    }

    //-------------创建小堆-----------------
    public void createBigHeap2(){
        //创建之前,先找到最后一个子节点的父母节点,然后每次通过循环遍历,前面的叶子节点的父母节点
        for(int parent = (usedSize - 1 - 1) / 2 ; parent >= 0 ; parent--){
            shiftDown2(parent , usedSize);
        }
    }

    //位置调整的方法
    /*
    end:就是每棵树结束的位置
    child:左孩子
    child + 1 : 右孩子
     */
    private void shiftDown2(int parent , int end){
        //根据根节点和孩子节点的关系,我们可以得到孩子节点的下标
        int child = 2*parent + 1;

        //===找左右最大值的下标:Child===
        //当我们的child＜end时说明没调完树的节点位置,大于end说明调完了
        while(child  < end){
            //根据树孩子节点和元素大小之间的关系:
            // --存在右孩子的条件是:右孩子的下标 < 树的总结点大小
            //在存在右孩子的条件下,我们才能去比较左右孩子的大小
            if(child + 1 < usedSize && elem[child] > elem[child + 1]){
                child++;
            }//****通过上面的条件获取 左右孩子中最小值的下标


            //===将根节点和左右最大值进行交换===
            //交换完以后;parent和child都需要往后遍历:parent = child ; child = 2*parent + 1 ;
            if(elem[child] < elem[parent]){
                //交换节点逻辑:
                //孩子大于父亲,交换两个节点
                swap2(child , parent);
                parent = child;//交换完,parent往孩子节点遍历
                child = 2 * parent + 1;//孩子节点也要往父母节点的子节点移动
            }else{
                break;
            }
        }
    }

    //交换下标的方法:
    private void swap2(int i , int j){
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }

}
